GNU bison

/*
 * Expression.h 
 * Definition of the structure used to build the syntax tree.
 */
#ifndef __EXPRESSION_H__
#define __EXPRESSION_H__
 
/**
 * @brief The operation type
 */
typedef enum tagEOperationType
{
    eVALUE,
    eMULTIPLY,
    ePLUS
}EOperationType;
 
/**
 * @brief The expression structure
 */
typedef struct tagSExpression
{
	EOperationType type;///< type of operation
 
	int value;///< valid only when type is eVALUE
	struct tagSExpression* left; ///< left side of the tree
	struct tagSExpression* right;///< right side of the tree
}SExpression;
 
/**
 * @brief It creates an identifier
 * @param value The number value
 * @return The expression or NULL in case of no memory
 */
SExpression* createNumber(int value);
 
/**
 * @brief It creates an operation
 * @param type The operation type
 * @param left The left operand
 * @param right The right operand
 * @return The expression or NULL in case of no memory
 */
SExpression* createOperation(
			EOperationType type,
			SExpression *left,
			SExpression *right);
 
/**
 * @brief Deletes a expression
 * @param b The expression
 */
void deleteExpression(SExpression *b);
 
#endif // __EXPRESSION_H__

/*
 * Expression.c 
 * Implementation of functions used to build the syntax tree.
 */
 
#include "Expression.h"
 
#include <stdlib.h>
 
/**
 * @brief Allocates space for expression
 * @return The expression or NULL if not enough memory
 */
static SExpression* allocateExpression()
{
	SExpression* b = malloc(sizeof *b);
 
	if( b == NULL ) return NULL;
 
	b->type = eVALUE;
	b->value = 0;
 
	b->left = NULL;
	b->right = NULL;
 
	return b;
}
 
SExpression* createNumber(int value)
{
	SExpression* b = allocateExpression();
 
        if( b == NULL ) return NULL;
 
	b->type = eVALUE;
	b->value = value;
 
	return b;
}
 
SExpression *createOperation( 
			EOperationType type,
                        SExpression *left,
                        SExpression *right)
{
	SExpression* b = allocateExpression();
 
	if( b == NULL ) return NULL;
 
	b->type = type;
	b->left = left;
	b->right = right;
 
	return b;
}
 
void deleteExpression(SExpression *b)
{
	if (b == NULL) return;
 
	deleteExpression(b->left);
	deleteExpression(b->right);
 
	free(b);
}

/*
 * TypeParser.h
 * Definition of the structure used internally by the parser and lexer
 * to exchange data.
 */
 
#ifndef __TYPE_PARSER_H__
#define __TYPE_PARSER_H__
 
#include "Expression.h"
 
/**
 * @brief The structure used by flex and bison
 */
typedef union tagTypeParser
{
	SExpression *expression;
	int value;
}STypeParser;
 
// define the type for flex and bison
#define YYSTYPE STypeParser
 
#endif // __TYPE_PARSER_H__

/*
 * ParserParam.h
 * Definitions of the parameters for the reentrant functions
 * of flex (yylex) and bison (yyparse)
 */
 
#ifndef __PARSERPARAM_H__
#define __PARSERPARAM_H__
 
#ifndef YY_NO_UNISTD_H
#define YY_NO_UNISTD_H 1
#endif // YY_NO_UNISTD_H
 
#include "TypeParser.h"
#include "Lexer.h"
#include "Expression.h"
 
/**
 * @brief structure given as argument to the reentrant 'yyparse' function.
 */
typedef struct tagSParserParam
{
	yyscan_t scanner;
	SExpression *expression;
}SParserParam;
 
// the parameter name (of the reentrant 'yyparse' function)
// data is a pointer to a 'SParserParam' structure
#define YYPARSE_PARAM	data
 
// the argument for the 'yylex' function
#define YYLEX_PARAM	((SParserParam*)data)->scanner
 
#endif // __PARSERPARAM_H__

%{
 
/*
 * Lexer.l file
 * To generate the lexical analyzer run: "flex --outfile=Lexer.c --header-file=Lexer.h Lexer.l"
 */
 
#include "TypeParser.h"
#include "Parser.h"
 
%}
 
%option reentrant noyywrap never-interactive nounistd
%option bison-bridge
 
LPAREN      "("
RPAREN      ")"
PLUS        "+"
MULTIPLY    "*"
 
NUMBER      [0-9]+
WS          [ \r\n\t]*
 
%%
 
{WS}            { /* Skip blanks. */ }
{NUMBER}        { sscanf(yytext,"%d",&yylval->value); return TOKEN_NUMBER; }
 
{MULTIPLY}      { return TOKEN_MULTIPLY; }
{PLUS}          { return TOKEN_PLUS; }
{LPAREN}        { return TOKEN_LPAREN; }
{RPAREN}        { return TOKEN_RPAREN; }
.               {  }
 
%%
 
int yyerror(const char *msg) { fprintf(stderr,"Error:%s\n",msg); return 0; }

%{
 
/*
 * Parser.y file
 * To generate the parser run: "bison --defines=Parser.h Parser.y"
 */
 
#include "TypeParser.h"
#include "ParserParam.h"
 
%}
 
%define api.pure
 
%left '+' TOKEN_PLUS
%left '*' TOKEN_MULTIPLY
 
%token TOKEN_LPAREN
%token TOKEN_RPAREN
%token TOKEN_PLUS
%token TOKEN_MULTIPLY
 
%token <value> TOKEN_NUMBER
 
%type <expression> expr
 
%%
 
input: 
	expr { ((SParserParam*)data)->expression = $1; }
	;
 
expr:
      expr TOKEN_PLUS expr { $$ = createOperation( ePLUS, $1, $3 ); }
    | expr TOKEN_MULTIPLY expr { $$ = createOperation( eMULTIPLY, $1, $3 ); }
    | TOKEN_LPAREN expr TOKEN_RPAREN { $$ = $2; }
    | TOKEN_NUMBER { $$ = createNumber($1); }
;
 
%%

#include "ParserParam.h"
#include "Parser.h"
#include "Lexer.h"
 
#include <stdio.h>
 
int yyparse(void *param);
 
static int initParserParam(SParserParam* param)
{
	int ret = 0;
 
	ret = yylex_init(&param->scanner);
	param->expression = NULL;
 
	return ret;
}
 
static int destroyParserParam(SParserParam* param)
{
	return yylex_destroy(param->scanner);
}
 
SExpression *getAST(const char *expr)
{
	SParserParam p;
	YY_BUFFER_STATE state;
 
	if ( initParserParam(&p) )
	{
		// couldn't initialize
		return NULL;
	}
 
	state = yy_scan_string(expr, p.scanner);
 
	if ( yyparse(&p) )
	{
		// error parsing
		return NULL;
	}
 
	yy_delete_buffer(state, p.scanner);
 
	destroyParserParam(&p);
 
	return p.expression;
}
 
int evaluate(SExpression *e)
{
	switch(e->type)
	{
		case eVALUE:
			return e->value;
		case eMULTIPLY:
			return evaluate(e->left) * evaluate(e->right);
		case ePLUS:
			return evaluate(e->left) + evaluate(e->right);
		default:
			// shouldn't be here
			return 0;
	}
}
 
int main(void)
{
	SExpression *e = NULL;
	char test[]=" 4 + 2*10 + 3*( 5 + 1 )";
	int result = 0;
 
	e = getAST(test);
 
	result = evaluate(e);
 
	printf("Result of '%s' is %d\n", test, result);
 
	deleteExpression(e);
 
	return 0;
}